package modele;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;





import modele.Batiment.Batiment;

public class Map implements Serializable{
	private static final long serialVersionUID = -7884965394902548908L;
	int nbrColonnes;
	int nbrLignes;
	int [][] terrain;//la valeur 1 signifie que la case est occupée
	
	public Map(int nbrColonnes, int nbrLignes)
	{
		assert nbrColonnes > 0;
		assert nbrLignes > 0;
		terrain = new int[nbrColonnes][nbrLignes];
		assert nbrColonnes == terrain.length;
		for(int i = 0; i < nbrColonnes; i++)
		{
			assert nbrLignes == terrain[i].length;
		}
		this.nbrColonnes = nbrColonnes;
		this.nbrLignes = nbrLignes;
		
		
	}
	
	/**
	 * évalue la validité d'une position (teste 0 <= position.getC() < nbrColonnes et 0 <= position.getL() < nbrLignes)
	 * @param position position a testé
	 * @return true si la position est valide, false sinon
	 */
	public boolean positionValide(Position position)
	{
		if(position.getC() < nbrColonnes && position.getC() >= 0 && position.getL() < nbrLignes && position.getL() >= 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	/**
	 * 
	 * @param pos position dont la fonction détermine si elle est libre sur la map
	 */
	public boolean estLibre(Position pos)
	{
		//System.out.println("estLibre : "+pos.toString());
		if(terrain[pos.getL()][pos.getC()] == 1)
			return false;
		return true;
	}
	
	
	/**
	 * 
	 * @param batiment Batiment à prendre en compte pour le calcul de chemin, le batiment doit avoir une position et une taille bien définie
	 */
	public void marquerCreationBatiment(Batiment batiment)
	{
		for(int i = 0; i < batiment.getLongueurCote(); i++)
			for(int j = 0; j < batiment.getLongueurCote(); j++)
			{
				this.terrain[batiment.getPosition().getC()+j][batiment.getPosition().getL()+i] = 1;
			}
	}
	
	
	/**
	 * retourne la distance entre deux cases arrondie au centième près
	 * @param c1 première case
	 * @param c2 seconde case
	 * @return distance entre c1 et c2 arrondie au centième
	 */
	public static Integer distance(Case c1, Case c2)
	{
		return Math.abs(c2.getX() - c1.getX()) + Math.abs(c2.getY() - c1.getY());
	}
	
	
	/**
	 * gauche, droite, bas, haut
	 * @param caseCourante Case dont les cases voisines sont à déterminer
	 * @return liste des cases voisines
	 */
	public ArrayList<Case> voisines(Case caseCourante, HashSet<Case> EI)
	{
		ArrayList<Case> voisines = new ArrayList<Case>();
		//on remplit la liste des voisines
		if(caseCourante.getX() != 0)//voisine de gauche
		{
			if(terrain[caseCourante.getX()-1][caseCourante.getY()] == 0 
			&& !EI.contains(new Case(caseCourante.getX()-1, caseCourante.getY())))//si elle n'est pas interdite
				voisines.add(new Case(caseCourante.getX()-1, caseCourante.getY()));
		}
		if(caseCourante.getX() < nbrColonnes-1)//voisine de droite
		{
			if(terrain[caseCourante.getX()+1][caseCourante.getY()] == 0 
			&& !EI.contains(new Case(caseCourante.getX()+1, caseCourante.getY())))//si elle n'est pas interdite
				voisines.add(new Case(caseCourante.getX()+1, caseCourante.getY()));
		}
		if(caseCourante.getY() != 0)//voisine du bas
		{
			if(terrain[caseCourante.getX()][caseCourante.getY()-1] == 0 && !EI.contains(new Case(caseCourante.getX(), caseCourante.getY()-1)))//si elle n'est pas interdite
				voisines.add(new Case(caseCourante.getX(), caseCourante.getY()-1));
		}
		if(caseCourante.getY() < nbrLignes-1)//voisine du haut
		{
			if(terrain[caseCourante.getX()][caseCourante.getY()+1] == 0 && !EI.contains(new Case(caseCourante.getX(), caseCourante.getY()+1)))//si elle n'est pas interdite
			{
				voisines.add(new Case(caseCourante.getX(), caseCourante.getY()+1));
			}
		}
		return voisines;
	}
	
	
	/**
	 * permet de trouver un chemin entre la case de départ et d'arrivée
	 * requis : les cases de départ et d'arrivée doivent être joignables (appartenir à la même composante connexe).
	 * @param caseDepart représente la case à partir de laquelle la recherche s'effectue, ses données membres precedente et distance seront modifiées
	 * @param caseArrivee représente la case à atteindre, ses coordonnées seront prises en compte et precedente sera modifiée
	 * @param compteurProfondeurRecursion représente le nombre maximal de récursion que peut effectuer l'algorithme
	 */
	public LinkedList<Direction> chercherChemin(Position positionDepart, Position positionArrivee, int compteurProfondeurRecursion)
	{
		Case caseDepart = new Case(positionDepart);
		Case caseArrivee = new Case(positionArrivee);
		if(caseDepart == caseArrivee)
			return new LinkedList<Direction>();
		ArrayListTriee<Case> EV = new ArrayListTriee<Case>();
		EV.inserer(caseDepart);
		HashSet<Case> EI = new HashSet<Case>();
		caseDepart.setDistance(new Distance(0, distance(caseDepart, caseArrivee)));
		return recherche(caseDepart, caseArrivee, EV, EI, compteurProfondeurRecursion);
	}
	
	/**
	 * requis : les cases de départ et d'arrivée doivent être différentes.
	 * requis : les cases de départ et d'arrivée doivent être joignables (appartenir à la même composante connexe).
	 * @param caseDepart représente la case à partir de laquelle la recherche s'effectue, ses données membres precedente et distance seront modifiées
	 * @param caseArrivee représente la case à atteindre, ses coordonnées seront prises en compte et precedente sera modifiée
	 * @param EV représente l'ensemble des cases éligibles pour être la prochaine jusqu'à l'arrivée ( EV = ensemble voisines )
	 * @param EI représente l'ensemble des cases interdites, c'est à dire les cases occupées par les bâtiments
	 * @param compteurProfondeurRecursion représente le nombre maximal de récursion que peut effectuer l'algorithme
	 */
	private LinkedList<Direction> recherche(Case caseDepart, Case caseArrivee, ArrayListTriee<Case> EV, HashSet<Case> EI, int compteurProfondeurRecursion)
	{
		if(EV.size() == 0)//on n'est pas situé dans la même composante connexe que la cible
		{
			return new LinkedList<Direction>();
		}
			
		Case caseCourante = EV.get(0);
		ArrayList<Case> voisines = voisines(caseCourante, EI);
		
		boolean caseArriveeAtteinte = false;
		for(int i = 0; (i < voisines.size() && caseArriveeAtteinte == false); i++)
		{
			voisines.get(i).setDistance(new Distance(caseCourante.getDistance().getAvant()+1, distance(caseCourante, caseArrivee)));
			if(voisines.get(i).getX() == caseArrivee.getX() && voisines.get(i).getY() == caseArrivee.getY())
				caseArriveeAtteinte = true;
		}
		
		if(caseArriveeAtteinte == true)//cas d'arrêt
		{
			caseArrivee.setPrecedente(caseCourante);
			LinkedList<Direction> directions = new LinkedList<Direction>();
			//on ajoute la direction de l'avant-dernière case à la dernière
			if(caseArrivee.getX() == caseCourante.getX()+1)
				directions.addFirst(Direction.DROITE);
			else if(caseArrivee.getX() == caseCourante.getX()-1)
				directions.addFirst(Direction.GAUCHE);
			else if(caseArrivee.getY() == caseCourante.getY()+1)
				directions.addFirst(Direction.HAUT);
			else
				directions.addFirst(Direction.BAS);
			//affichage
			Case tmpParcours = caseCourante;
			while(!(tmpParcours.getX() == caseDepart.getX() && tmpParcours.getY() == caseDepart.getY()))
			{
				//tmpParcours.afficherPartiellement();
				if(tmpParcours.getX() == tmpParcours.getPrecedente().getX()+1)
					directions.addFirst(Direction.DROITE);
				else if(tmpParcours.getX() == tmpParcours.getPrecedente().getX()-1)
					directions.addFirst(Direction.GAUCHE);
				else if(tmpParcours.getY() == tmpParcours.getPrecedente().getY()+1)
					directions.addFirst(Direction.HAUT);
				else
					directions.addFirst(Direction.BAS);
				tmpParcours = tmpParcours.getPrecedente();
			}
			return directions;
			
		}
		else//récursion
		{
			for(int i = 0; i < voisines.size(); i++)
			{
				voisines.get(i).setPrecedente(caseCourante);
			}
			EV.remove(caseCourante);
			for(int i = 0; i < voisines.size(); i++)
			{
				EV.inserer(voisines.get(i));
			}
			EI.add(new Case(caseCourante.getX(), caseCourante.getY()));
			compteurProfondeurRecursion = compteurProfondeurRecursion - 1;
			if(compteurProfondeurRecursion < 1)
			{
				//System.out.println("AVERTISSEMENT : LA RECURSION A DEPASSE LA PROFONDEUR AUTORISEE, AVORTEMENT DE LA RECURSION");
				return new LinkedList<Direction>();
			}
			
			return recherche(caseDepart, caseArrivee, EV, EI, compteurProfondeurRecursion);
			
		}
	}
	
	
	/**
	 * permet de trouver un chemin entre la case de départ et d'arrivée
	 * requis : les cases de départ et d'arrivée doivent être joignables (appartenir à la même composante connexe).
	 * @param caseDepart représente la case à partir de laquelle la recherche s'effectue, ses données membres precedente et distance seront modifiées
	 * @param caseArrivee représente la case à atteindre, ses coordonnées seront prises en compte et precedente sera modifiée
	 * @param compteurProfondeurRecursion représente le nombre maximal de récursion que peut effectuer l'algorithme
	 */
	public LinkedList<Direction> chercherCheminSansDerniereCase(Position positionDepart, Position positionArrivee, int compteurProfondeurRecursion)
	{
		Case caseDepart = new Case(positionDepart);
		Case caseArrivee = new Case(positionArrivee);
		if(caseDepart == caseArrivee)
			return new LinkedList<Direction>();
		ArrayListTriee<Case> EV = new ArrayListTriee<Case>();
		EV.inserer(caseDepart);
		HashSet<Case> EI = new HashSet<Case>();
		caseDepart.setDistance(new Distance(0, distance(caseDepart, caseArrivee)));
		LinkedList<Direction> l = recherche(caseDepart, caseArrivee, EV, EI, compteurProfondeurRecursion);
		//if(l.size() > 0)
		//	l.remove(l.size()-1);
		LinkedList<Direction> l2 = new LinkedList<Direction>();
		for(int i = l.size()-1; i >= 0; i--)
		{
			l2.add(l.get(i));
		}
		
		
		//Case tmp = new Case(positionDepart.getC(), positionDepart.getL());
		//for(int i = 0; i < l2.size(); i++)
		//{
		//	tmp.plus(l2.get(i));
		//	System.out.println(tmp);
		//}
		
		
		
		return l2;
	}
	
	
	public void afficher()
	{
		System.out.println("================");
		for(int i = nbrLignes-1; i >= 0; i--)
		{
			for(int j = 0; j < nbrColonnes; j++)
			{
				
				System.out.print(terrain[j][i]+" ");
			}
			System.out.println();
		}
		System.out.println("================");
			
	}
	
}
